package _01_动态数组;

import java.util.Arrays;

public class _34_在排序数组中查找元素的第一个和最后一个位置 {

    public static void main(String[] args) {

        _34_在排序数组中查找元素的第一个和最后一个位置 v = new _34_在排序数组中查找元素的第一个和最后一个位置();

        int[] ins = new int[]{5, 7, 7, 8, 8, 10, 11};

        System.out.println(v.binarySearchLeft(ins, 7));
    }


    // 右边界, 第一个大于等于
    public int binarySearchRight(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; // 定义target在左闭右闭的区间里，[left, right]
        int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) { // 当left==right，区间[left, right]依然有效
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else { // 当nums[middle] == target的时候，更新left，这样才能得到target的右边界
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }

    // 左边界，第一个小于等于
    public int binarySearchLeft(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; // 定义target在左闭右闭的区间里，[left, right]
        int leftBorder = -1; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) { // 当left==right，区间[left, right]依然有效
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] >= target) {
                leftBorder = middle;
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else { // 当nums[middle] == target的时候，更新left，这样才能得到target的右边界
                left = middle + 1;

            }
        }
        return leftBorder;
    }

    // 查找右边元素，遍历
    public int[] searchRange(int[] nums, int target) {
        int[] results = new int[]{-1, -1};
        int begin = 0;
        int end = nums.length - 1;
        int searchLeftIndex = -1;
        while (begin <= end) {
            int mid = begin + end >> 1;
            if (nums[mid] >= target) {
                searchLeftIndex = mid;
                end = mid - 1;
            } else {
                begin = mid + 1;
            }
        }
        if (searchLeftIndex == -1 || nums[searchLeftIndex] != target) {
            return results;
        }
        // 存在值, 向右查找最后一个值
        results[0] = searchLeftIndex;
        for (int i = searchLeftIndex; i < nums.length; i++) {
            if (nums[i] == target) {
                results[1] = i;
            } else {
                break;
            }
        }
        return results;
    }

}
